
/************************************************************
 **  Ariel Morelli                                         **
 **  Carlos Pereira Lopes Filho                            **
 **  Gustavo Buzogany Eboli                                **
 **  Programacao Concorrente                               **
 **  Algoritmo Dijkstra em paralelo com MPI e OpenMP.      **
 **                                                        **
 ************************************************************/

#include <stdio.h>
#include <stdlib.h>

#define INFINITO 9000000

int num_nos;
int **matriz, *minimos;

/* Encontra o adjacente minimo */
int minimo_adjacente(char *abertos, int origem, int *distancia){

    int menor = INFINITO;
    int i, j, menor_i=-1;
    
    /* Escolhe o vertice adjacente a origem, com a menor distancia */
    for(i=0;i<num_nos;i++){
        if(distancia[i]!=INFINITO && distancia[i]<menor && abertos[i]==1){
            menor = distancia[i];
            menor_i = i;
        }
    }

    /* Caso nao exista um vertice com estas caracteristicas, retorna (-1) */
    if(menor_i==-1){
        return -1;
    }

    abertos[i]=0;

    return menor_i+1;
}

void inicializa_matriz(){
    
    int i, j;

    matriz = (int**)malloc(num_nos*sizeof(int*));
    
    for(i=0;i<num_nos;i++){
        matriz[i] = (int*) malloc (num_nos*sizeof(int));
    }
    
    for(i=0;i<num_nos;i++){
        for(j=0;j<num_nos;j++){
            matriz[i][j]=INFINITO;
        }
    }
}


int getMaior(int *vector, int size){
    int i;
    int maior;
    maior=0;
    for(i=0;i<size;i++){
        if(vector[i]>maior)
            maior = vector[i];
    }
    return maior;
}

int getMenor(int *vector, int size){
    int i;
    int menor;
    menor=INFINITO;
    for(i=0;i<size;i++){
        if(vector[i]<menor)
            menor = vector[i];
    }
    return menor;
}

int existem_abertos(char *abertos){
    int i;
    for(i=0;i<num_nos;i++){
        if(abertos[i]==1)
            return 1;
    }
    return 0;
}


int Dijkstra(char *abertos, int origem){

    int i, u, v, aux, caso_teste=0;
    int *distancia = (int*) malloc (num_nos*sizeof(int));

    matriz[origem-1][origem-1]=0;

    /* Inicializa os valores */
    for(i=0;i<num_nos;i++){
        distancia[i] = INFINITO; 
    }

    distancia[origem-1]=0;
    
    u=origem;
    
    while(existem_abertos(abertos)){

        u = minimo_adjacente(abertos, u, distancia);

        if(u==-1){
            return;
        }
        u--;

        /* Para cada v adjacente a u */
        for(v=0;v<num_nos;v++){
            if(matriz[v][u]<INFINITO){
                aux = distancia[u] + matriz[u][v];
                if(aux<distancia[v]){
                    distancia[v] = aux;
                }
            }
        }

        /* Marca o adjacente minimo como fechado */
        abertos[u]=0;
        u++; caso_teste++;
    }
    aux = getMaior(distancia, num_nos);
    return aux;
}

void abre_todos(char *abertos){
    int i;
    for(i=0;i<num_nos;i++){
        abertos[i]=1;
    }
}

int main(){

    int num_arestas, i, j, a, b, size;
    char *abertos;
    scanf("%d %d", &num_nos, &num_arestas);
    int *maiores = (int*)malloc(num_nos*sizeof(int));

    abertos = (char*)malloc(num_nos*sizeof(char));
    abre_todos(abertos);


    inicializa_matriz();

    for(i=0;i<num_arestas;i++){
        scanf("%d %d %d", &a, &b, &size);
        /* Se uma rua liga A a B, ela liga B a A */
        matriz[a-1][b-1] = size;
        matriz[b-1][a-1] = size;
    }

    for(i=0;i<num_nos;i++){
        maiores[i] = Dijkstra(abertos, i+1);
        abre_todos(abertos);
    }

    printf("%d ", getMenor(maiores, num_nos));
    printf("\n");

    return 0;

}
